#ifndef _OVERLAP_H_
#define _OVERLAP_H_

#include <vector>
#include <algorithm>
#include <iterator>
#include <map>
#include <limits>

#include <boost/math/special_functions/fpclassify.hpp>
// CGAL 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Vector_2.h>
#include <CGAL/Ray_2.h>
#include <CGAL/intersections.h>
#include <CGAL/squared_distance_2.h>
#include <CGAL/Boolean_set_operations_2.h>

#include "polytope.h"
#include "piecewise_func.h"

namespace Nesting
{
	/*
	** Express the overlap between two polytopes, polygons or polyhedron
	** One is moving and the other static
	*/
	class Overlap
	{

	public:

		//Overlap(const Nesting_polytope* move_polytope, const Nesting_polytope* static_polytope) 
		//		: mv_polytope(move_polytope), st_polytope(static_polytope) { }

		virtual Overlap& operator+=(const Overlap& other) = 0;
		virtual double min(double& argmin) const = 0;
		virtual double min(double mint, double maxt, double& argmin) const = 0;
		virtual ~Overlap() { };
		virtual bool empty() const = 0;
		virtual double volume_at(double t) const = 0;
		//virtual double miu_value_at(double t) const = 0;
		// parameters where two polytopes begin/end intersecting
		//virtual double start_intersec_t() const = 0;
		//virtual double end_intersect_t() const = 0;
	};


	/*
	** Overlap between two 2D polygons
	*/
	class Overlap_2 : public Overlap
	{

	public:

		typedef CGAL::Vector_2<CGAL::Exact_predicates_inexact_constructions_kernel> Vector_2;
		typedef CGAL::Ray_2<CGAL::Exact_predicates_inexact_constructions_kernel>	Ray_2;
		typedef CGAL::Point_2<CGAL::Exact_predicates_inexact_constructions_kernel>	Point_2;
		typedef CGAL::Line_2<CGAL::Exact_predicates_inexact_constructions_kernel>	Line_2;
		typedef CGAL::Segment_2<CGAL::Exact_predicates_inexact_constructions_kernel>	Segment_2;

	public:

		Overlap_2() { }
		// only support translation field, i.e. trans_field is always constant at every point
		Overlap_2(const Nesting_polygon *move_polygon, const Nesting_polygon *static_polygon, const Vector_2& trans_field, double penalty = 0.0);

		~Overlap_2() { }

		double min(double& argmin) const;
		double min(double mint, double maxt, double& argmin) const;

		Overlap& operator+=(const Overlap& other) ;
		
		bool empty() const { return overlap_area.constant_zero(); }
		double volume_at(double t) const { return overlap_area.value_at(t); }
		//double miu_value_at(double t) const { std::fabs(volume_at(t)) / (1 + p); }
		// debug
		void gl_draw_keypoints() const;

	private:

		Quad_piecewise_func overlap_area;
		Quad_piecewise_func extended_area;
		double p; // penalty

	private: //private type definitions

		typedef Nesting_polygon::Edge_const_iterator Edge_const_iterator;
		enum Edge_type { POSITIVE, NEGATIVE, NEUTRAL } ;
		typedef std::pair<Edge_const_iterator, Edge_type> Signed_edge;

		// helper class
		struct Keypoint
		{
			double t;
			Edge_const_iterator mv_e;
			Edge_const_iterator st_e;
			enum TYPE {POSITIVE_POSITIVE, POSITIVE_NEGATIVE, NEGATIVE_POSITIVE, NEGATIVE_NEGATIVE} type;
			Quad_piecewise_func::Coeff coeff;
			Point_2 pos; // position where the two edges start to form a region area

			Keypoint() { t = 0.0; }
			Keypoint(double offset, Edge_const_iterator move_edge, Edge_const_iterator static_edge, TYPE seg_type_pair)
				: t(offset), mv_e(move_edge), st_e(static_edge), type(seg_type_pair), coeff(0.0, 0.0, 0.0) { }
			
		};

		struct IsEmpytKeypoint 
		{
			bool operator()(const Keypoint& keypoint) const
			{
				return keypoint.coeff.a == 0.0 && keypoint.coeff.b == 0.0 && keypoint.coeff.c == 0.0;
			}
		};

		struct Keypoint_cmp : public std::binary_function<const Keypoint&, const Keypoint&, bool>
		{
			bool operator()(const Keypoint& kp0, const Keypoint& kp1) const
			{
				return kp0.t < kp1.t;
			}
		};

		static void make_keypoints(const Signed_edge& mv_edge, const Signed_edge& st_edge, const Vector_2& v, std::vector<Keypoint>& keypoints);

		inline static Keypoint::TYPE keypoint_type(const Signed_edge& mv_edge, const Signed_edge& st_edge)
		{
			if (mv_edge.second == POSITIVE && st_edge.second == POSITIVE)
				return Keypoint::POSITIVE_POSITIVE;
			else if (mv_edge.second == POSITIVE && st_edge.second == NEGATIVE)
				return Keypoint::POSITIVE_NEGATIVE;
			else if (mv_edge.second == NEGATIVE && st_edge.second == POSITIVE)
				return Keypoint::NEGATIVE_POSITIVE;
			else
				return Keypoint::NEGATIVE_NEGATIVE;
		}
		
		// debug
		//std::vector<Keypoint> keypoints;
	};


}
#endif